A typical data storage system includes processing circuitry and a set of disk drives. In general, the processing circuitry stores data in the set of disk drives and retrieves data from the set of disk drives on behalf of one or more external hosts. The processing circuitry typically includes a set of processor circuit boards (or simply CPU boards), a set of memory circuit boards (or simply memory boards), and an interconnect (e.g., a backplane) that enables the CPU boards and the memory boards to communicate with each other. The memory boards provide volatile storage space which the CPU boards use as both input/output (I/O) memory and system memory. The I/O memory, which is commonly referred to as the I/O cache, temporarily stores data received from an external host for subsequent storage in the set of disk drives, as well as temporarily stores data read from the set of disk drives for subsequent transmission to an external host. The system memory stores key memory constructs (i.e., data structures) of the data storage system.
One memory construct is the Least-Recently-Used (LRU) queue which includes a list of LRU entries identifying blocks (e.g., 512 bytes) of the I/O cache for storing data. The LRU queue is a data structure which is typically arranged as a doubly linked list that identifies the I/O cache blocks in order from the most recently used to the least recently used. That is, the LRU queue includes a series of LRU entries beginning with a first LRU entry identifying the most recently used block of the I/O cache, followed by a second LRU entry identifying the next most recently used block, and so on. The series of LRU entries ends with a last LRU entry identifying the least recently used block of the I/O cache.
Typically, when an external host sends a read request to the data storage system (e.g., a request to read cached data), a CPU board responds to the request by, among other things, (i) transferring a copy of the requested data from a block of the I/O cache to the host and (ii) updating the LRU queue. To update the LRU queue, the CPU board performs, through the interconnect, a series of load and store operations on the memory board storing the LRU queue. In particular, the CPU board locates the LRU entry identifying the I/O cache block containing the data and moves, or promotes, that entry to the beginning of the LRU queue to indicate that the block is now the most recently used block in the I/O cache. Further details of how the CPU board updates the LRU queue will now be provided.
Recall that the LRU queue is a doubly linked list having a series of LRU entries. Moving a particular LRU entry to the beginning of the LRU queue typically involves multiple LRU operations. First, a CPU board identifies the adjacent preceding LRU entry and the adjacent succeeding LRU entry by reading forward and reverse pointers of the particular LRU entry. Second, the CPU board removes the particular LRU entry from the series of LRU entries by (i) reading, modifying and storing the forward pointer of the adjacent preceding LRU entry and (ii) reading, modifying and storing the reverse pointer of the adjacent succeeding LRU entry. Third, the CPU board finds the first LRU entry in the LRU queue by reading a head pointer of the LRU queue. Next, the CPU board adds the particular LRU entry to the beginning of the LRU queue by reading, modifying and storing the reverse pointer of first LRU entry, and modifying and storing the forward and reverse pointers of the particular LRU entry (the reverse pointer of the particular LRU entry can be set to NULL or set to point to the particular LRU entry itself since it is now the beginning entry). Finally, the CPU board indicates that the particular LRU entry is now at the beginning of the LRU queue for a subsequent LRU access operation by modifying the head pointer of the LRU queue. The block identified by the particular LRU entry is now identified as the most recently used block of the I/O cache.
When a host sends a request to write data, a CPU board typically responds by (i) finding an available I/O cache block for storing the data, (ii) placing the data into that block, and (iii) updating the LRU queue. The process of finding an available block typically involves the CPU board accessing the ending entry in the LRU queue to identify the least recently used block of the I/O cache. The process of updating the LRU queue typically involves the CPU board moving the ending entry of the LRU queue (i.e., the entry identifying the block that now contains the written data) to the beginning of the LRU queue thus indicating that the block containing the data is now the most recently used block of the I/O cache. Moving the ending entry of the LRU queue involves performing a series of read-modify-write operations on the LRU queue in a manner similar to that just described for reading an I/O cache block.
When the data storage system includes multiple CPU boards that can concurrently operate on behalf one or more external hosts (e.g., to increase data storage system throughput), the multiple CPU boards must share access to the LRU queue. To this end, the data storage system typically employs data structure sharing techniques (i.e., techniques for coordinating access to a shared data structure) in order to prevent the CPU boards from inadvertently accessing the LRU queue simultaneously. For example, suppose that a particular CPU board wishes to identify the least recently used block in the I/O cache and store data in that block on behalf of a host. To this end, the CPU board typically locks the LRU queue, identifies the least recently used block based on the last entry in the LRU queue, stores the data in that block, moves the last entry in the LRU queue to the beginning of the LRU queue so that the LRU queue now identifies that block as the most recently used block, and then unlocks the LRU queue. Such locking and unlocking of the LRU queue prevents another CPU board from concurrently accessing the LRU queue, and typically involves the use of a standard locking mechanism (e.g., semaphores, bit test-and-set operations, etc.). Accordingly, conflict situations (e.g., multiple CPU boards attempting to store data in the same I/O cache block, one CPU board writing data while another CPU reads data from the same block, etc.) are avoided.